package com.shawn.algorithm.search;

public class BinarySearch {

	public static int binarySearch(int[] a, int value) {
		int low = 0;
		int high = a.length - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] == value) {
				return mid;
			} else if (a[mid] < value) {
				low = mid + 1;
			} else {
				high = mid - 1;
			}
		}

		return -1;
	}

	public static int search(int[] a, int value) {
		return search(a, 0, a.length - 1, value);
	}

	private static int search(int[] a, int low, int high, int value) {
		if (low > high) {
			return -1;
		}
		int mid = low + ((high - low) >> 1);
		if (a[mid] == value) {
			return mid;
		} else if (a[mid] < value) {
			return search(a, mid + 1, high, value);
		} else {
			return search(a, low, mid - 1, value);
		}
	}

	/**
	 * 查找第一个值等于给定值的元素
	 */
	public int bsearchFirst(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] > value) {
				high = mid - 1;
			} else if (a[mid] < value) {
				low = mid + 1;
			} else {
				/*
					对于a[mid] == value的情况
					如果mid == 0,那这个元素就是数组的第一个元素，自然也就是我们需要的第一个元素
					如果mid != 0，我们需要判断a[mid - 1]是否==value，
						因为，数组是有序的，如果a[mid-1]都不等于value，证明mid之前的元素都比mid的小
						如果a[mid-1]等于value,说明a[mid]不是我们需要的元素，我们需要从[low,mid-1]之间查找。
				 */
				if ((mid == 0) || (a[mid - 1] != value)) {
					return mid;
				} else {
					high = mid - 1;
				}
			}
		}
		return -1;
	}

	/**
	 * 查找最后一个值等于给定值的元素
	 */
	public int bsearchLast(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] > value) {
				high = mid - 1;
			} else if (a[mid] < value) {
				low = mid + 1;
			} else {
				/*
					对于a[mid] == value的情况
					如果mid == n - 1,那这个元素就是数组的最后一个元素，自然也就是我们需要的最后一个元素
					如果mid != n - 1,我们需要判断a[mid + 1]是否==value，
						因为，数组是有序的，如果a[mid + 1]都不等于value，证明mid之后的元素都比mid的大
						如果a[mid + 1]等于value,说明a[mid]不是我们需要的元素，我们需要从[mid + 1,high]之间查找。
				 */
				if ((mid == n - 1) || (a[mid + 1] != value)) {
					return mid;
				} else {
					low = mid + 1;
				}
			}
		}
		return -1;
	}

	/**
	 * 查找第一个值大于等于给定值的元素
	 */
	public int bsearchGreaterFirst(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] >= value) {
				/*
					对于a[mid] >= value
						如果mid == 0,那这个元素就是数组的第一个元素，自然也就是我们需要的第一个元素
						如果mid != 0,我们需要判断a[mid-1]是否 < value。
							如果 < value,因为数组是有序的，a[mid - 1] < value <= a[mid]，所以mid就是我们需要的元素
							否则我们需要从[low,mid - 1]这个区间查找。
				 */
				if ((mid == 0) || (a[mid - 1] < value)) {
					return mid;
				} else {
					high = mid - 1;
				}
			} else {
				low = mid + 1;
			}
		}
		return -1;
	}

	/**
	 * 查找最后一个小于等于给定值的元素
	 */
	public int bsearchLessLast(int[] a, int n, int value) {
		int low = 0;
		int high = n - 1;
		while (low <= high) {
			int mid = low + ((high - low) >> 1);
			if (a[mid] > value) {
				high = mid - 1;
			} else {
				/*
					对于a[mid] <= value
						如果mid == n - 1,那这个元素就是数组的最后一个元素，自然也就是我们需要的最后一个元素
						如果mid != n - 1,我们需要判断a[mid+1]是否 > value。
							如果>value,因为数组是有序的，a[mid] <= value < a[mid + 1] ，所以mid就是我们需要的元素
							否则我们需要从[mid + 1,high]这个区间查找。
				 */
				if ((mid == n - 1) || (a[mid + 1] > value)) {
					return mid;
				} else {
					low = mid + 1;
				}
			}
		}
		return -1;
	}

}
